package algorithms.leaning.class11;

import common.bean.TreeNode;
import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 层序遍历，记录所有节点
 *
 * @author guichang
 * @date 2021/6/9
 */

@SuppressWarnings("all")
public class Code1_二叉树_层序遍历 {

    public static void main(String[] args) {

        TreeNode treeNode = MyUtil.createTreeNode(1, 2, 3, 4, 5, 6, 7, 8, 9);
        // 层序遍历 [1, 2, 3, 4, 5, 6, 7, 8, 9]
        MyUtil.print(sequenceTraversal(treeNode));
    }

    public static List<Integer> sequenceTraversal(TreeNode head) {
        List<Integer> list = new ArrayList<>();
        if (head == null) {
            return list;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(head);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return list;
    }

}